class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        int postorderSize = postorder.size();
        if(postorderSize == 0)  return true;
        /*
        二叉搜索树后序遍历的特点：每个序列最后一个数字是其根节点；
        从序列第一个元素开始搜索，在找到第一个大于根节点的元素之前的子序列均为根节点的左子序列，
        该元素到根节点间子序列为根节点右子序列，若存在其右子序列的节点小于根节点的元素则返回false;
        通过根节点划分其左右子序列，再递归判断其子序列；
        */
        return judge(postorder, 0, postorderSize - 1);
    }

    bool judge(vector<int>& postorder, int first, int last){
        if(first == last)  return true;
        else if(first > last)  return false;

        int medium = first;
        while(postorder[medium] < postorder[last]){
            ++medium;
        }
        //查看右子序列中是否有小于根节点的情况
        int medium_copy = medium + 1;
        while(medium_copy < last){
            if(postorder[medium_copy] < postorder[last])  return false;
            ++medium_copy;
        }

        if(medium == last){
            return judge(postorder, first, last - 1);  //右序列为空
        }else if(medium == first){
            return judge(postorder, first, last - 1);  //左序列为空
        }else{
            return judge(postorder, first, medium - 1) && judge(postorder, medium, last - 1);
        }
    }
};